package demo1;

import sun.plugin.javascript.navig4.Link;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


//层序遍历
public class Solution {
    public TreeNode createBinaryTree() {
        TreeNode treeNode1 = new TreeNode('A');
        TreeNode treeNode2 = new TreeNode('B');
        TreeNode treeNode3 = new TreeNode('D');
        TreeNode treeNode4 = new TreeNode('E');
        TreeNode treeNode5 = new TreeNode('H');
        TreeNode treeNode6 = new TreeNode('C');
        TreeNode treeNode7 = new TreeNode('F');
        TreeNode treeNode8 = new TreeNode('G');
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode6;
        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;
        treeNode4.right = treeNode5;
        treeNode6.left = treeNode7;
        treeNode6.right = treeNode8;
        return treeNode1;
    }


    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */

        public List<List<Integer>> levelOrder1(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<>();
            if (root == null) return ret;

            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                int size = queue.size(); // size的大小就是每一层的个数
                List<Integer> list = new ArrayList<>();
                while (size != 0) {
                    TreeNode cur = queue.poll();
                    //list.add(cur.val); 去掉注释
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                    size--;
                }
                ret.add(list);
            }
            return ret;
        }

    public void levelOrder(TreeNode root) {
       // List<Integer> link = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
}